Internet Service Provider networks are generally multi-homed and have multiple external Border Gateway Protocol (eBGP) links with external subnets. The peering between the neighbors provides an abundance of alternate paths at a border of an autonomous system towards external subnets. However, an internal BGP (iBGP) peer typically is merely aware of one best path to each of the peer's neighbors.
Existing path-vector-routing protocols, such as the Border Gateway Protocol (BGP), require routers to advertise only a best path to a given destination. Because the path-vector-routing protocols are not designed to allow routers to advertise a second best path or other next-best paths, routers cannot fully exploit existing redundancies of underlying network infrastructure.
Using route reflectors is one of the main reasons for poor path diversity within an autonomous system. In a network with a route reflector, even if the route reflector learns that diverse routes exist to a given destination, the route reflector may only reflect the best path to that destination.
A technique termed the “Best External” approach, described in the internet-draft document “draft-marques-idr-best-external-01.txt,” has claimed to improve the path diversity within an autonomous system. However, the diverse paths generated according to the “Best External” approach are not redistributed to all the routers inside the autonomous system and thus, the majority of the routers know merely a single external route to each of their neighbors.
The “Diverse Path” approach described in the internet draft “draft-raszuk-diverse-bgp-path-dist-00,” proposes adding shadow route reflectors for each primary route reflector to calculate and advertise the second, third, fourth, and other (nth) best paths. The primary route reflector is called a first plane or a best-path route reflector, and computes and advertises the best path. The first shadow route reflector is called a second plane route reflector, and computes and advertises the second best path. The second shadow route reflector is called a third plane route reflector, and computes and advertises the third best path. The nth shadow route reflector is termed the nth plane route reflector, and computes and advertises the nth best path. The first, second, third, . . . nth best paths are diverse as they have different next hops, so that the remote provider edge router can have multiple paths with different exit points for the same prefix.
However, in the “Diverse Path” approach if the route reflectors at different planes are not co-located due to a possible variance in an Interior Gateway Protocol (IGP) metric, a proper calculation of the diverse paths cannot be guaranteed Δn existing route reflector can be used as a shadow route reflector, but even if peering is established between a first plane route reflector and a second plane route reflector, the units may not exchange best paths due to route reflector rules. Further, even if the units do exchange best paths, the units may be unable to distinguish whether a received best path originated from the ith plane route reflector or some other route reflector that is not participating in diverse path calculation.
The best path calculation in the “Diverse Path” approach requires a significant number of iterations. For example, the second best path calculation at a second plane route reflector requires two iterations; the third best path calculation at a third plane route reflector requires three iterations, and so forth.
The “Add Path” approach described in “draft-ietf-idr-add-paths-00” requires significant modifications to the routing protocol. Further, Add Path is not backward compatible and requires upgrades throughout the network to function.